home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / glimpse-2.1 / agrep / agrep.algorithms < prev    next >
Encoding:
Text File  |  1995-05-16  |  2.6 KB  |  49 lines
  1. /* Copyright (c) 1994 Sun Wu, Udi Manber, Burra Gopal.  All Rights Reserved. */
  2. The implementation of agrep includes the following algorithms.
  3. Except for exact matching of simple patterns, for which we use 
  4. a simple variation of the Boyer-Moore algorithm, 
  5. all the algorithms (listed below) were designed by Sun Wu and Udi Manber.
  6.  
  7. 1. bitap:  The most general algorithm inside agrep.
  8.        It supports many extensions such as approximate regular expression 
  9.        pattern matching, non-uniform costs, simultaneous matching of 
  10.        multiple patterns, mixed exact/approximate matching, etc.
  11.        The algorithm is described in agrep.ps.1.
  12.  
  13. 2. mgrep:  A sub-linear expect-time algorithm for matching a set of patterns.
  14.        It assumes that the set of patterns contains k patterns, and that
  15.        the shortest pattern is of size m.
  16.        See agrep.ps.2 for a brief description of the algorithm.
  17.  
  18. 3. amonkey: a Boyer-Moore style algorithm for approximate pattern matching.
  19.        let b = log_c (2*m), where c is the size of alphabet set.
  20.        In the preprocessing, a table is built to determine whether
  21.        a given substring of size b is in the pattern.
  22.        Suppose we are looking for matches with at most k errors.
  23.        The search is done in two passes.
  24.        In the first pass (the filtering pass), the areas in the text
  25.        that have a possibility to contain the matches are marked.
  26.        The second pass finds the matches in those marked areas.
  27.        The search in the first pass is done in the following way.
  28.        Suppose the end position of the pattern is currently aligned with 
  29.        position tx in the text.
  30.        The algorithm scans backward from tx until either (k+1) blocks
  31.        that do not occur in the pattern have been scanned, or
  32.        the scan has passed position (tx-m+k).
  33.        In the former case, pattern is shifted forward to align
  34.        the beginning position of the pattern with one character after
  35.        the position in the text where the scan was stopped.
  36.        In the latter case, we marked tx-m to tx+m as a candidate area.
  37.  
  38. 4. mmonkey: Combining the mgrep algorithm with a partition technique, we
  39.        have an algorithm with the same time complexity as amonkey.
  40.        For ASCII text and pattern, this algorithm is faster than amonkey.
  41.        The principle of the partition technique is as follows.
  42.        Let A and B be two strings of size m. 
  43.        If we partition A into (k+1) blocks, then the distance between 
  44.        A and B is > k if none of the blocks of A occur in B. 
  45.        This implies that to match A with no more than k errors, 
  46.        B has to contain a substring that matches exactly one block of A.
  47.        A brief description can be found in agrep.ps.2.
  48.  
  49.